import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode, Integer>(root, 1));
        int ret = 0;
        while(!q.isEmpty()){
            // 获取这一层的宽度
            Pair<TreeNode, Integer> p1 = q.get(0);
            Pair<TreeNode, Integer> p2 = q.get(q.size() - 1);
            int width = p2.getValue() - p1.getValue() + 1;
            ret = ret > width ? ret : width;

            // 让下一层进队
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode, Integer> p : q){
                TreeNode node = p.getKey();
                int value = p.getValue();
                if(node.left != null){
                    tmp.add(new Pair<TreeNode, Integer>(node.left, value * 2));
                }
                if(node.right != null){
                    tmp.add(new Pair<TreeNode, Integer>(node.right, value * 2 + 1));
                }
            }
            q = tmp;
        }
        return ret;
    }
}